//
// Created by LiuYou on 2021/12/3.
//

#include <iostream>
#include <vector>
#include <iterator>
#include <random>


static int randomNumberFromTheRange(int left, int right) {
    std::random_device randomDevice;
    std::default_random_engine randomEngine( randomDevice());
    std::uniform_int_distribution<> uniformIntDistribution( left, right );
    return uniformIntDistribution( randomEngine );
}


/**
 * @brief 构建一个堆(大顶堆)。
 * @param arr 数组。
 * @param index 当前是哪个位置想要加入到堆结构中。
 */
static void heapInsert(std::vector<int>& arr, int index) {
    int parentIndex = (index - 1) / 2;

    while (parentIndex >= 0) {
        if (arr[parentIndex] < arr[index]) {
            std::swap( arr[index], arr[parentIndex] );

            index = parentIndex;
            parentIndex = (index - 1) / 2;
        } else {
            break;
        }
    }
}


static void heapify(std::vector<int>& arr, int index, int heapSize) {
    int leftChildIndex = index * 2 + 1;
    while (leftChildIndex < heapSize) {
        int largestIndex{};
        if ((leftChildIndex + 1 < heapSize) && arr[leftChildIndex + 1] > arr[leftChildIndex]) {
            largestIndex = leftChildIndex + 1;
        } else {
            largestIndex = leftChildIndex;
        }
        if (arr[largestIndex] > arr[index]) {
            std::swap( arr[largestIndex], arr[index] );

            index = largestIndex;
            leftChildIndex = index * 2 + 1;
        } else {
            break;
        }
    }
}


static void heapSort(std::vector<int>& arr) {
    if (arr.empty() || arr.size() == 1) {
        return;
    }

    for (int i = 0; i < arr.size(); ++i) {
        heapInsert( arr, i );
    }

    int heapSize = arr.size();

    while (heapSize > 0) {
        std::swap( arr[0], arr[--heapSize] );
        heapify( arr, 0, heapSize );
    }
}


int main(int argc, char** argv) {
    {
        std::vector<int> arr( 10 );
        for (auto& item: arr) {
            item = randomNumberFromTheRange( 0, 100 );
        }

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << std::endl;

        for (int i = 0; i < arr.size(); ++i) {
            heapInsert( arr, i );
        }

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << std::endl;
    }

    std::cout << "=====================[ heap sort ]=====================" << std::endl;

    {
        std::vector<int> arr( 10 );
        for (auto& item: arr) {
            item = randomNumberFromTheRange( 0, 100 );
        }

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << std::endl;

        heapSort( arr );

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << std::endl;
    }


    return 0;
}
